1. Field of the Invention
The present invention relates to digital data communication, storage and retrieval. More specifically, the present invention relates to systems for detecting and correcting errors in digital data communication, storage and retrieval systems.
While the present invention is described herein with reference to illustrative embodiments for particular applications, it should be understood that the invention is not limited thereto. Those having ordinary skill in the art and access to the teachings provided herein will recognize additional modifications, applications, and embodiments within the scope thereof and additional fields in which the present invention would be of significant utility.
2. Description of the Related Art
In the communication, storage and retrieval of digital data, errors arise due to noise, media defects, component aging and other parameters. Numerous schemes have been developed to detect and correct these errors. One early approach involved the simple retransmission of the data on the detection of an error condition. Unfortunately, in a noisy environment, frequent retransmission may be required. Frequent retransmission severely limits the throughput or bandwidth of the system.
Accordingly, numerous coding schemes have been developed to correct detected errors without retransmission. In these coding schemes, data bits are grouped into symbols of one or more data bits with one or more redundant symbols to facilitate error detection and correction. The number of data and redundant symbols used and the type of encoder and decoder used varies with the coding scheme selected.
In the design and/or selection of an optimal coding scheme, the designer is forced into a tradeoff between error correction power, decoder circuit complexity and bandwidth. That is, the greater the correction power of the code, the higher the "overhead" in terms of the number of redundant symbols, and the lower the sustained data rate of actual symbols. By way of example, a 10% increase in overhead may result in a 10% decrease in system throughput.
In addition, the greater the correction power of the code and the resulting higher number of redundant symbols employed, the greater the complexity of the circuitry in the decoder system.
Accordingly, many error detecting and correcting systems have heretofore been designed to provide the degree of error correcting power required for a given maximum error case. Reed-Solomon codes have been found to be well suited and are frequently selected as the code of choice. Reed-Solomon codes are a well known subset of the class of Bose-Chaudhuri-Hocquenghem (BCH) codes.
A Reed-Solomon code is typically the code of choice for at least two major reasons. First, Reed-Solomon codes are MDS (maximum-distance-separatable) codes which implies optimal performance for many error conditions encountered. Secondly, Reed-Solomon codes are sufficiently well behaved that exact performance can be predicted if the input error distribution can be described.
For example, if the input symbol probability of error is `p` and each symbol's error status is independent of all other symbols, it is a simple matter to compute the number of symbols in error in any randomly selected codeword (assuming an (n,k) code and i=0 to n symbols in error): EQU P(errors)=C(n,i)*p.sup.i *(1-p).sup.n-i
where C(n,i)=the number of combinations of n things take i at a time.
Now consider the case where n=28, k=20 and p is equal to 0.0001. Using the above equation, the following approximate probabilities may be computed:
P(0 errors)=9.9720378 * 0.1 PA1 P(1 error)=2.7924498 * 0.001 PA1 P(2 errors)=3.7701843 * 0.000001 PA1 P(3 errors)=3.2678198 * 0.000000001 PA1 P(4 errors)=2.0425916 * 0.000000000001
The probabilities are approximately 3 orders of magnitude smaller for the i+1th error condition than for the ith error condition.
Error correction decoders require many more steps (and time) to process (detect and correct) progressively more errors. These decoders are configured to operate in a maximum decode mode, i.e., always decode for worst case condition even when there are fewer errors or no errors. Such decoders can either represent the throughput bottlenecks for the systems in which they are embedded or require multiple decoders to run in parallel (a hardware cost and circuit reliability penalty) to achieve the desired throughput rate. As can be seen from the example above, such a penalty can be incurred for something that occurs very, very infrequently.
As an alternative, another approach involves the transmission of data at a first high data rate and a low level of correcting power. On detection of an error, the data is retransmitted at a lower rate with a more powerful error detecting and correcting code. To maintain a minimum desired throughput, the system must either operate at a higher clock speed or use multiple parallel decoders. Increases in clock speed are difficult to achieve due to the high costs associated with faster technologies and limitations on clocking speed of all technologies. As a result, use of multiple decoders tends to be a preferred approach. However, decoders are generally a costly and complex component of the system. Accordingly, improvements in throughput afforded by the use of multiple decoders are often offset by the high cost associated therewith.
Accordingly, there is a need in the art for an inexpensive, high performance error detecting and correcting system which is capable of handling multiple errors with high throughput.